package LC;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/next-permutation/description/
 * Implement next permutation, which rearranges numbers into
 * the lexicographically next greater permutation of numbers.
 * If such arrangement is not possible, it must rearrange it
 * as the lowest possible order (ie, sorted in ascending order).
 * The replacement must be in-place, do not allocate extra memory.
 * Here are some examples. Inputs are in the left-hand column and
 * its corresponding outputs are in the right-hand column.
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 */
public class LC_031_NextPermutation_Perm_Array {
    public static void main(String[] args) {
        int[] a = {6, 5, 4, 8, 7, 5, 1};
        Solution.nextPermutation(a);
        System.out.println(Arrays.toString(a));
    }

    static class Solution {
        static void nextPermutation(int[] nums) {
            //数组的长度
            int idx = nums.length - 1;

            //从后往前找递减区域8，下标为3
            while (idx > 0 && nums[idx] <= nums[idx - 1])
                idx--;

            //如果全部是逆序3 2 1，则排成正序的即可1 2 3
            if (idx == 0) {
                Arrays.sort(nums);
                return;
            }

            //从后往前，在递减区域8, 7, 5, 1中第一个，比第一个非递减区域数字4大的数字5
            int second = Integer.MAX_VALUE, secondidx = Integer.MAX_VALUE;

            //从后往前，在递减区域8, 7, 5, 1中第一个，比第一个非递减区域数字4大的数字5
            for (int i = nums.length - 1; i >= idx - 1; i--) {
                if (nums[i] > nums[idx - 1] && nums[i] < second) {
                    second = nums[i];
                    secondidx = i;
                }
            }

            System.out.println("idx--------" + idx);
            System.out.println("idx-1--------" + (idx - 1));
            System.out.println("nums[idx - 1]---" + nums[idx - 1]);
            System.out.println("second-----" + second);
            System.out.println("secondidx-----" + secondidx);

            //交换 第一个非递减区域的数4 和 递减区域里面第一个比他大的数字5
            nums[idx - 1] = nums[idx - 1] ^ nums[secondidx];
            nums[secondidx] = nums[idx - 1] ^ nums[secondidx];
            nums[idx - 1] = nums[idx - 1] ^ nums[secondidx];

            //重排8, 7, 4, 1
            Arrays.sort(nums, idx, nums.length);
        }
    }

}
